package com.lds.offer.demo;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;
import java.util.TreeSet;

/**
 * @description: Offer II 075. 数组相对排序
 * @author: lds
 * @create: 2022-10-11 15:03
 **/
public class Offer_075_数组相对排序 {

    //https://leetcode.cn/problems/0H97ZC/

    /**
     * 遍历数组a，将值和对应次数设为键值对存于map中
     * 遍历数组b，通过b中的元素作为key获取map中的值（该值即为数组a的元素个数），循环次数输出元素到res结果集中
     * 输出完成后将该键值对从map中移除
     * 将map中剩余的key进行排序（剩下的key即为存在a数组但不存在b数组的元素）
     * 循环keySet，通过键值对获取该元素的个数，将其添加在res结果集中
     */

    public static void main(String[] args) {
        int[] a = new int[] {2,21,43,38,0,42,33,7,24,13,12,27,12,24,5,23,29,48,30,31};
        int[] b = new int[] {2,42,38,0,43,21};
        sort(a,b);
    }

    public static void sort(int[] a,int[] b) {
        int[] res = new int[a.length];
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < a.length; i++) {
            if (map.containsKey(a[i])) {
                map.put(a[i],map.get(a[i]) + 1);
            } else {
                map.put(a[i],1);
            }
        }
        int x = 0;
        for (int i = 0; i < b.length; i++) {
            if (map.containsKey(b[i])) {
                for (int j = 0; j<map.get(b[i]); j++) {
                    res[x] = b[i];
                    x++;
                }
                map.remove(b[i]);
            }
        }

        Set<Integer> keySet = map.keySet();
        TreeSet set = new TreeSet(keySet);
        set.comparator();
        for (Object o : set) {
            for (Integer i = 0; i < map.get(o); i++) {
                res[x] = (Integer) o;
                x++;
            }
        }
        System.out.println(Arrays.toString(res));
    }

}
